package algorithms.a02sortbasic;

import algorithms.utis.AlgorithmsUtis;
import algorithms.utis.SortTestHelper;

import java.util.*;

public class InsertionSort {

    // 我们的算法类不允许产生任何实例
    private InsertionSort() {
    }

    /**
     * 原始的，性能较低的插入排序算法
     * 原因：swap次数多，耗时
     *
     * @param arr
     * @date: 2018/2/5 8:57
     * @author: 王昊然
     */
    public static void sortLower(Comparable[] arr) {

        int n = arr.length;
        for (int i = 1; i < n; i++) {

            // 寻找元素arr[i]合适的插入位置

            // 写法1
//            for( int j = i ; j > 0 ; j -- )
//                if( arr[j].compareTo( arr[j-1] ) < 0 )
//                    AlgorithmsUtis.swap( arr, j , j-1 );
//                else
//                    break;

            // 写法2
            for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--)
                AlgorithmsUtis.swap(arr, j, j - 1);

        }
    }

    /**
     * 优化后的插入排序
     *
     * @param arr
     * @date: 2018/2/5 8:58
     * @author: 王昊然
     */
    public static void sort(Comparable[] arr) {

        int n = arr.length;
        for (int i = 1; i < n; i++) {

            //现将当前要处理的元素复制出来备用
            Comparable e = arr[i];

            // 寻找元素arr[i]合适的插入位置
            int j;
            for (j = i; j > 0 && arr[j - 1].compareTo(e) > 0; j--) {
                arr[j] = arr[j - 1];
            }

            arr[j] = e;
        }
    }

    public static void sort(Comparable[] arr, int left, int right) {

        for (int i = left + 1; i <= right; i++) {
            Comparable e = arr[i];
            int j = i;
            for (; j > left && arr[j - 1].compareTo(e) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = e;
        }

    }

    // 测试InsertionSort
    public static void main(String[] args) {

        int N = 20000;
        //Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 3); //1排序数组数值范围小，插入排序优势明显
        Integer[] arr = SortTestHelper.generateNearlyOrderedArray(N, 200);//2排序数组近乎有序的，插入排序优势明显
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);

        System.out.print("忽略--------");
        SortTestHelper.testSort(InsertionSort.class, arr);//testSort第一次计算比较慢，不作参考
        System.out.println();

        SortTestHelper.testSort(SelectionSort.class, arr2);
        SortTestHelper.testSort(InsertionSort.class, arr3);
    }


}